1862F - Magic Will Save the World - CodeForces Solution

#include <bits/stdc++.h>
using namespace std;

vector<bool> cur;

bool check(int time, int f, int w, int sum) {
    long long fval = 1LL * time * f, wval = 1LL * time * w;
    
    int closestVal = 0;
    for(long long s = min(0LL+sum, fval); s >= 0; s--) {
        if(cur[s]) {
            closestVal = s;
            break;
        }
    }
    int remVal = sum - closestVal;
    return (wval >= remVal);
}

void solve() {
    int n, f, w;
    cin >> w >> f >> n;
    vector<int> arr(n);
    int sum = 0;
    for(int i = 0; i < n; i++) {
        cin >> arr[i]; sum += arr[i];
    }

    vector<bool> dp(sum+1, false);
    cur.clear();
    cur.resize(sum+1, false);
    dp[0] = true;
    dp[arr[0]] = true;
    for(int i = 1; i < n; i++) {
        for(int s = 1; s <= sum; s++) {
            cur[s] = dp[s];
            if(s-arr[i] >= 0)
                cur[s] = cur[s] | dp[s-arr[i]];
        }
        dp = cur;
    }
    cur = dp;

    int l = 0, r = sum;
    while(r - l > 1) {
        int mid = l + (r - l) / 2;
        if(check(mid, f, w, sum))
            r = mid;
        else   
            l = mid;
    }
    cout << r << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
	cin.tie(NULL);
    int t = 1;
    cin >> t;
    while(t-- > 0) solve();
    return 0;
}